package 算法.leetcode.str;

/**
 * 最长回文子串
 * @author lchenglong
 * @date 2022/2/10
 */
@SuppressWarnings("all")
public class HuiWen {

    public static void main(String[] args) {
        HuiWen huiWen = new HuiWen();
        System.out.println(huiWen.longestPalindrome("abbabde"));
    }
    public String longestPalindrome(String s) {
        //边界条件
        if(s.length()<2){
            return s;
        }
        // 保存最长回文串的起止索引
        int start = 0,end = 0;
        for(int i=0;i<s.length();i++){
            int len1 = expand(s,i,i);
            int len2 = expand(s,i,i+1);
            int len = Math.max(len1,len2);
            if(len>end-start){
                start = i -(len-1)/2;
                end = i+len/2;
            }
        }
        return s.subSequence(start,end+1).toString();
    }

    /**
     * 扩散算法
     *
     * @param s
     * @param left
     * @param right
     * @return
     */
    private int expand(String s,int left,int right){
        while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
            --left;
            ++right;
        }
        // 最后两边各多加1 需要减去
        return right-left-1;
    }
}
